1. Field of the Invention
The invention relates to flash memories, and more particularly to shift errors of data output by flash memories.
2. Description of the Related Art
To prevent data from damage during storage, a data storage device usually encodes data to convert the data to an error correction code before the data is written to a memory of the data storage device. The error correction code is then stored in the memory. When the data storage device retrieves the error correction code from the memory, the error correction code must be decoded to convert the error correction code back to the original data. If it is determined during the decoding process, that the error correction code comprises error bits, the data storage device corrects the error bits during the decoding process to generate original data without error bits.
Referring FIG. 1, a block diagram of a data storage device 104 is shown. The data storage device 104 is coupled to a host 102. The data storage device 104 comprises a controller 106 and a flash memory 108. When the host 102 requests the data storage device 104 to read data, the controller 106 sends a chip enable signals CE to the flash memory 108 to enable the flash memory 108. The controller 106 then sends a series of read enable pulses RE to the flash memory 108. The flash memory 108 then reads error correction codes stored therein and outputs the error correction codes according to the read enable pulses RE. The controller 106 then decodes the error correction codes to obtain data. If the error correction codes comprise error bits, the controller 106 corrects the error bits of the error correction codes to obtain correct data. Finally, the controller 106 sends the data to the host 102 to complete read operations.
Ordinary error correction codes, such as Bose, Ray-Chaudhuri, and Hocquenghem (BCH) codes and Reed-Solomon (RS) codes, are cyclic codes. Error bits are ordinarily corrected according to cyclic codes. When cyclic codes comprise shift errors, a controller 106 cannot detect shift errors in the cyclic codes, and the cyclic codes with shift errors are taken as correct codes. Shift errors therefore negatively impact data correctness of cyclic codes, and degrade performance of the data storage device 104.
Referring to FIG. 2, a schematic diagram of shift errors of an error correction code received by the controller 106 from the flash memory 108 is shown. At time t1, the controller enables the chip enable signal CE to enable the flash memory 108. After a time period T has passed, the controller 106 sends a first read enable pulse 202 to the flash memory 108 at time t2. In ordinary cases, the flash memory 108 should read an error correction code according to the read enable pulse 202 and send a first byte of the error correction code to the controller 106 before a next read enable pulse 204 is sent at time t3. In some exceptional cases, the flash memory 108, however, may require a longer time for the enabling process and may not acknowledge the read enable pulse 202 sent at time t2. The flash memory therefore reads nothing and outputs no data to a data bus connected between the controller 106 and the flash memory 108 during time t2 to t3. When the controller 106 reads the data bus connected between the controller 106 and the flash memory 108 at the time t3, the controller 108 therefore only obtains a byte comprising error bits.
The controller 106 then sends a second read enable pulse 204 to the flash memory 108 at time t3, and then reads a data byte D01 of an error correction code output by the flash memory 108. The controller 106 then sends a third read enable pulse 206 to the flash memory 108, and then reads a data byte D02 of the error correction code output by the flash memory 108. The controller 106 therefore obtains an error correction code comprising an error data byte 210 and correct data bytes D01 and D02. However, the controller 106 does not determine that an error data byte 210 exists.
Referring to FIG. 3A, a schematic diagram of data stored in a page of a flash memory 108 is shown. Assume that a page of the flash memory 108 can store data of 8 K bytes, the data comprises 8 code words C1, C2, . . . , C8, and each code word has a 1 K-byte data amount. Also, each code word C1, C2, . . . , C8 comprises a data portion M1, M2, . . . , M8 and a parity portion P1, P2, . . . P8. Referring to FIG. 3B, a schematic diagram of a data page with shift errors output by the flash memory 108 is shown. Assume that the controller 106 receives a data page comprising 8 1 K-byte code words C1′, C2′, . . . , C8′ with shift errors from the flash memory 108. Because the controller 106 receives an erroneous first byte E, the code word C1′ comprises an error byte E, a data portion M1, and a first portion P11 of a parity P1. Similarly, the code word C2′ comprises a second portion P12 of the parity P1, a data portion M2, and a first portion P21 of a parity P2. All code words C1′, C2′, . . . , C8′ received by the controller 106 therefore comprise a shift-error byte. Because the code words C1′, C2′, . . . , C8′ are cyclic codes, the controller 106 cannot detect the shift errors of the code words C1′, C2′, . . . , C8′, and the code words C1′, C2′, . . . , C8′ are determined to be correct. Thus, performance of the data storage device 104 is degraded due to shift errors of the decoded data.